package main

import (
	"fmt"
	"log"
	"math"
)

type subject interface {
	register(observer)
	deRegister(observer)
	notifyAll()
}

type item struct {
	observers []observer
	name      string
}

func (i *item) register(o observer) {
	i.observers = append(i.observers, o)
}

func (i *item) deRegister(o observer) {
	i.observers = i.remove(i.observers, o)
}

func (i *item) notifyAll() {
	for _, o := range i.observers {
		o.update(i.name)
	}
}

func (i *item) remove(observers []observer, o observer) []observer {
	for j, ob := range observers {
		if ob.getId() == o.getId() {
			observers = append(observers[:j], observers[j+1:]...)
			return observers
		}
	}
	return observers
}

type observer interface {
	update(string)
	getId() string
}

type consumer struct {
	id string
}

func (c *consumer) update(name string) {
	log.Printf("listen from %s, id is %s", name, c.id)
}

func (c *consumer) getId() string {
	return c.id
}

type collection interface {
	createIterator() iterator
}

type user struct {
	Name string
}

type userCollection struct {
	users []*user
}

func (c *userCollection) createIterator() iterator {
	return &userIterator{
		users: c.users,
	}
}

type iterator interface {
	hasNext() bool
	getNext() (*user, bool)
}

type userIterator struct {
	index int
	users []*user
}

func (u *userIterator) hasNext() bool {
	if u.index < len(u.users) {
		return true
	}
	return false
}

func (u *userIterator) getNext() (*user, bool) {
	if u.hasNext() {
		userRes := u.users[u.index]
		u.index++
		return userRes, true
	}
	return nil, false
}

func do() {
	//观察者模式
	i := &item{
		name: "testName",
	}
	consumerObserver1 := &consumer{
		id: "consumerObserver-1",
	}
	i.register(consumerObserver1)
	consumerObserver2 := &consumer{
		id: "consumerObserver-2",
	}
	i.register(consumerObserver2)
	i.notifyAll()
	//迭代器模式
	users := []*user{{"张三"}, {"李四"}, {"王五"}}
	userCol := &userCollection{users}
	userIter := userCol.createIterator()

	for i := 0; i < len(users); i++ {
		r, _ := userIter.getNext()
		log.Print(r.Name)
	}
}

type topK interface {
	int | int8 | int16 | int32 | int64
}

type minHeap[T topK] struct {
	data     []T
	capacity int
}

type listT interface {
	int | string
}

type list[T listT] struct {
	val  T
	next *list[T]
}

func main() {
	// 寻找topK, 零钱兑换
	s := []int{3, 499, 2, 34, 12, 5, 8, 9, 100}
	getTopK(s, 3)
	head := sliceToList(s)
	newHead := reversal(head)
	printList(newHead)
	// l > len(list)
	lr := reversalLtoR(newHead, 17, 27)
	printList(lr)
}

func reversalLtoR[T listT](head *list[T], l, r int) *list[T] {
	if head == nil || l >= r {
		return head
	}
	dummyHead := &list[T]{next: head}
	prev := dummyHead
	for i := 1; i < l; i++ {
		if prev == nil {
			return reversal(head)
		}
		prev = prev.next
	}
	cur := prev.next
	for j := 0; j < r-l; j++ {
		next := cur.next
		cur.next = next.next
		next.next = prev.next
		prev.next = next
	}
	return dummyHead.next
}

func printList[T listT](head *list[T]) {
	for head != nil {
		fmt.Printf("%v->", head.val)
		head = head.next
	}
	fmt.Println("nil")
}

func reversal[T listT](head *list[T]) *list[T] {
	var prev *list[T]
	for head != nil {
		next := head.next
		head.next = prev
		prev = head
		head = next
	}
	return prev
}

func sliceToList[T listT](s []T) *list[T] {
	if len(s) == 0 {
		return nil
	}
	head := &list[T]{val: s[0]}
	current := head
	for _, v := range s[1:] {
		current.next = &list[T]{val: v}
		current = current.next
	}
	return head
}

func newMinHeap[T topK](k int) *minHeap[T] {
	return &minHeap[T]{
		data:     make([]T, 0, k),
		capacity: 0,
	}
}

func (h *minHeap[T]) top() T {
	if h.capacity == 0 {
		return -1
	}
	return h.data[0]
}

func (h *minHeap[T]) insert(val T) {
	if h.capacity < cap(h.data) {
		h.data = append(h.data, val)
		h.capacity++
		h.up(h.capacity - 1)
	} else if val > h.data[0] {
		h.data[0] = val
		h.down(0)
	}
}

func (h *minHeap[T]) up(index int) {
	parent := (index - 1) / 2
	for index > 0 && h.data[parent] > h.data[index] {
		h.data[parent], h.data[index] = h.data[index], h.data[parent]
		index = parent
		parent = (index - 1) / 2
	}
}

func (h *minHeap[T]) down(index int) {
	small := index
	left := index*2 + 1
	right := index*2 + 2
	if left < h.capacity && h.data[left] < h.data[index] {
		small = left
	}
	if right < h.capacity && h.data[right] < h.data[index] {
		small = right
	}
	if small != index {
		h.data[small], h.data[index] = h.data[index], h.data[small]
		h.down(small)
	}
}

func getTopK[T topK](s []T, k int) T {
	h := newMinHeap[T](k)
	for i := 0; i < k; i++ {
		h.insert(s[i])
	}
	for i := k; i < len(s); i++ {
		if s[i] > h.top() {
			h.insert(s[i])
		}
	}
	return h.top()
}

func change(coins []int, target int) []int {
	l := len(coins)
	if l == 0 {
		return nil
	}
	var (
		path = make([]int, target+1)
		dp   = make([]int, target+1)
	)

	for i := 1; i <= target; i++ {
		dp[i] = math.MaxInt32
		for _, coin := range coins {
			if i >= coin && dp[i-coin] != math.MaxInt32 && dp[i-coin]+1 < dp[i] {
				path[i] = coin
				dp[i] = dp[i-coin] + 1
			}
		}
	}
	if dp[target] == math.MaxInt32 {
		return nil
	}
	var res []int
	for target > 0 {
		res = append(res, path[target])
		target -= path[target]
	}
	return res
}

func subjectsEqTarget(s []int, target int) [][]int {
	var (
		res  [][]int
		path []int
	)
	var backTrack func(int, []int, int)
	backTrack = func(start int, path []int, target int) {
		for i := start; i < len(s); i++ {
			if i > start && s[i] == s[i-1] {
				continue
			}
			if s[i] > target {
				break
			}
			path = append(path, s[i])
			backTrack(i+1, path, target-s[i])
			path = path[:len(path)-1]
		}
		if target == 0 {
			res = append(res, path)
		}
	}
	backTrack(0, path, target)
	return res
}

func getMax(a, b int) int {
	if a > b {
		return a
	}
	return b
}
